/*
 * Implement an algorithm to determine if a string has all unique characters.
 * What if you can not use additional data structures?
 */

public class Chapter1_1 {
//	public static void main(String []args)
//	{
//		boolean result1, result2, result3;
//		result1 = isCharactersUniqueWithoutDS("abceed");
//		System.out.println("result1 is " + result1);
//		
//		result2 = isCharactersUniqueWithDS("abced");
//		System.out.println("result2 is " + result2);
//		
//		result3 = isCharactersUnique("abcedfg");
//		System.out.println("result3 is " + result3);
//	}
	
	//time complexity is O(n*n), n is the length of string
	public static boolean isCharactersUniqueWithoutDS(String _str)
	{
		for(int i = 0 ; i < _str.length(); i++)
		{
			for(int j = 0; j < _str.length(); j++)
			{
				if(_str.charAt(i) == _str.charAt(j))
					return false;
			}
		}
		return true;
	}
	
	//assume char is ASCII
	//time complexity is O(n), n is the length of string
	//space complexity is O(C)
	public static boolean isCharactersUniqueWithDS(String _str)
	{
		int char_set[] = new int[256];
		int letterIndex;
		for(int i = 0; i < _str.length(); i++)
		{
			letterIndex = _str.charAt(i);
			if(char_set[letterIndex] != 0)
				return false;
			else
				char_set[letterIndex]++;
		}
		return true;
	}
	
	//assume the string is only lower case 'a' through 'z' which only asks for 26 bits to record
	//time complexity is O(n), n is the length of string
	
	public static boolean isCharactersUnique(String _str)
	{
		int checker = 0;
		for(int i = 0; i < _str.length(); i++)
		{
			int val = _str.charAt(i);
			if((checker & (1<<val)) > 0) return false;
			checker = checker|(1<<val);
		}
		return true;
	}
	
}
